 /*******************************************************************************
  * Copyright (c) 2004, 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.utils;

 import org.eclipse.core.runtime.Assert;

 /**
  * A cache that keeps a collection of at most maximumCapacity+threshold entries.
  * When the number of entries exceeds that limit, least recently used entries are removed
  * so the current size is the same as the maximum capacity.
  */
 public class Cache {
     public class Entry implements KeyedHashSet.KeyedElement {
         Object cached;
         Object key;
         Entry next;
         Entry previous;
         long timestamp;

         public Entry(Object key, Object cached, long timestamp) {
             this.key = key;
             this.cached = cached;
             this.timestamp = timestamp;
         }

         public boolean compare(KeyedHashSet.KeyedElement other) {
             if (!(other instanceof Entry))
                 return false;
             Entry otherEntry = (Entry) other;
             return key.equals(otherEntry.key);
         }

         /* Removes this entry from the cache */
         public void discard() {
             unchain();
             cached = null;
             entries.remove(this);
         }

         public Object getCached() {
             return cached;
         }

         public Object getKey() {
             return key;
         }

         public int getKeyHashCode() {
             return key.hashCode();
         }

         public Entry getNext() {
             return next;
         }

         public Entry getPrevious() {
             return previous;
         }

         public long getTimestamp() {
             return timestamp;
         }

         public boolean isHead() {
             return previous == null;
         }

         public boolean isTail() {
             return next == null;
         }

         /* Inserts into the head of the list */
         void makeHead() {
             Entry oldHead = head;
             head = this;
             next = oldHead;
             previous = null;
             if (oldHead == null)
                 tail = this;
             else
                 oldHead.previous = this;
         }

         public void setCached(Object cached) {
             this.cached = cached;
         }

         public void setTimestamp(long timestamp) {
             this.timestamp = timestamp;
         }

         public String toString() {
             return key + " -> " + cached + " [" + timestamp + ']'; //$NON-NLS-1$ //$NON-NLS-2$
 }

         /* Removes from the linked list, but not from the entries collection */
         void unchain() {
             // it may be in the tail
 if (tail == this)
                 tail = previous;
             else
                 next.previous = previous;
             // it may be in the head
 if (head == this)
                 head = next;
             else
                 previous.next = next;
         }
     }

     KeyedHashSet entries;
     Entry head;
     private int maximumCapacity;
     Entry tail;
     private double threshold;

     public Cache(int maximumCapacity) {
         this(Math.min(KeyedHashSet.MINIMUM_SIZE, maximumCapacity), maximumCapacity, 0.25);
     }

     public Cache(int initialCapacity, int maximumCapacity, double threshold) {
         Assert.isTrue(maximumCapacity >= initialCapacity, "maximum capacity < initial capacity"); //$NON-NLS-1$
 Assert.isTrue(threshold >= 0 && threshold <= 1, "threshold should be between 0 and 1"); //$NON-NLS-1$
 Assert.isTrue(initialCapacity > 0, "initial capacity must be greater than zero"); //$NON-NLS-1$
 entries = new KeyedHashSet(initialCapacity);
         this.maximumCapacity = maximumCapacity;
         this.threshold = threshold;
     }

     public void addEntry(Object key, Object toCache) {
         addEntry(key, toCache, 0);
     }

     public Entry addEntry(Object key, Object toCache, long timestamp) {
         Entry newHead = (Entry) entries.getByKey(key);
         if (newHead == null)
             entries.add(newHead = new Entry(key, toCache, timestamp));
         newHead.cached = toCache;
         newHead.timestamp = timestamp;
         newHead.makeHead();
         int extraEntries = entries.size() - maximumCapacity;
         if (extraEntries > maximumCapacity * threshold)
             // we have reached our limit - ensure we are under the maximum capacity
 // by discarding older entries
 packEntries(extraEntries);
         return newHead;
     }

     public Entry getEntry(Object key) {
         return getEntry(key, true);
     }

     public Entry getEntry(Object key, boolean update) {
         Entry existing = (Entry) entries.getByKey(key);
         if (existing == null)
             return null;
         if (!update)
             return existing;
         existing.unchain();
         existing.makeHead();
         return existing;
     }

     public Entry getHead() {
         return head;
     }

     public Entry getTail() {
         return tail;
     }

     private void packEntries(int extraEntries) {
         // should remove in an ad-hoc way to get better performance
 Entry current = tail;
         for (; current != null && extraEntries > 0; extraEntries--) {
             current.discard();
             current = current.previous;
         }
     }

     public long size() {
         return entries.size();
     }

     public void discardAll() {
         entries.clear();
     }

     public void dispose() {
         discardAll();
         entries = null;
     }
 }

